#include<stdio.h>
#include<stdlib.h>
struct node
{
int value;
struct node * next;
};
struct node * new = NULL;
struct node * new1 = NULL;
/*struct node *add(struct node **list, int n)
	{
	  	struct node * new_node = NULL;

 		new_node = malloc(sizeof(struct node));
 		new_node->value=n; 
 		new_node->next = *list;
 		*list = new_node;
	}
*/
struct node *add(struct node *list, int n)
	{
	  struct node *new_node = malloc(sizeof(struct node));
	  if (new_node == NULL) {
	    printf("Error: malloc failed in add_to_list\n");
	    exit(0);
	  }
	  new_node->value = n;
	  new_node->next = list;
	  return new_node;
	}

struct node * display(struct node * list)
	{
	  struct node * p = list;
	  for (; p != NULL; p = p->next)
	    	printf("%d , ",p->value);
	  return NULL;
	}
int count(struct node *list, int l)
{
		struct node * p;
		int count = 0;
		for(p=list; p !=NULL;p=p->next)
		{
			if(p->value==l)
			count++;
		}
		return count;
		
}

struct node * insert(int a, int b,struct node * list)
{
		struct node * r = malloc(sizeof(struct node));
		struct node * t = malloc(sizeof(struct node));
		struct node * temp = malloc(sizeof(struct node));
		r=list;
		int i;
		for(i=1;i<b;i++)
		{
          		t=r;   /* t will be holding previous value */
		        r=r->next;
	        }
       			temp->value=a;
       		        t->next=temp;
       			t=temp;
       			t->next=r;
}

struct node *delete(struct node *list, int n)
{
  struct node *cur, *prev;
	  
  for (cur = list, prev = NULL;
       cur != NULL && cur->value != n;
       prev = cur, cur = cur->next)
    ;
  if (cur == NULL) 
    return list;             /* n was not found */
  if (prev == NULL)
    list = list->next;       /* n is in the first node */
  else
    prev->next = cur->next;  /* n is in some other node */
  free(cur);
  return list;
}

reverse(struct node *list)
{
   struct node *m, *n,*s;
   m=list;
   n=NULL;
  while(m!=NULL)
 {
   s=n;
   n=m;
  m=m->next;
  n->next=s;
 }
   new=n;
}
sort ( int n )
{
	int i, j, k, temp ;
	struct node *p, *q ;
	p = new ;	
	for ( i = 0 ; i < n - 1 ; i++ )
	{
		q = p -> next;
		for ( j = i + 1 ; j < n ; j++ )
		{
			if ( p -> value > q -> value )
			{
				temp = p -> value ;
				p -> value= q -> value ;
				q -> value = temp ;
			}
			q = q -> next ;
		}
		p = p -> next ;
	}
	int g;
	printf("Do you want it in 1. Ascending order or 2. Descending order (Press 1 or 2) : " );
	scanf("%d",&g);
	if(g==1)
	{
	 printf("The sorted list is : \n");
	 display(new);
	}
	if(g==2)
	{
		reverse(new);
		printf("The sorted list is : \n");
		display(new);
	}	
}

struct node * extend(struct node *list1, struct node * list2)
{
	struct node *s;
	s=list1;
	while(s->next!=NULL)
		s=s->next;
	s->next=list2;
	return(list1);
}
/*sort(struct node * first,int n)
{
struct node *p;
int z;
int a[n];
for(z=0,p=first;p!=NULL;p=p->next,z++)
{
	a[z]=p->value;
}
int i,j,t;  
         for(i=n-2;i>=0;i--)  
         {  
            for(j=0;j<=i;j++)  
  
                  {  
                    if(a[j]>a[j+1])  
                                    {  
                                      t=a[j];  
                                     a[j]=a[j+1];  
                                     a[j+1]=t;  
                                    }  
                   }  
         
  
           }//end for 1.
int g;
printf("Do you want it in 1. Ascending order or 2. Descending order (Press 1 or 2) : " );
scanf("%d",&g);
for(z=0,p=new;p!=NULL;z++,p=p->next)
	{
		p->value=a[z];
	}
if(g==1)
	display(new);
if(g==2)
	reverse(new);
	display(new);
}
*/



int main()
{	
int y=1;

do
{ 	system("clear");
	int ch;
	printf("\n1.Add elements\n2.Display elements.\n3.[list.remove(x)] Delete the first occurence of an element.\n4.[list.count(x)] Count the number of times a particular element appears in the list .\n5.[list.insert(i,x)] Insert an element at a particular position .\n6.[list.append(x)] Append at the end of the list .\n7.[list.index(x)] Display the index of the first occurence of a particular element.\n8.[list.reverse()] Reverses the elements in the list.\n9.[list.sort()] Sort the list\n10.[list.extend(L)] Extend the list by adding another list.\n11.[list.pop(i)] pop the ith element.\n12.Exit.\nEnter your choice :  ");
	scanf("%d",&ch);
	switch(ch)
	{
		case 1 :
			{
			int k;
			printf("\nEnter the element you want to add to the list : \n");
			scanf("%d",&k);
			new = add(new,k);
			printf("\nIf you want to continue enter 1, else press any other number : ");
			scanf("%d",&y);
			break;}

		case 2 :
			{
			printf("\nThe elements of the linked list are \n");
			display(new);
			printf("\nIf you want to continue enter 1, else press any other number : ");
			scanf("%d",&y);		
			break;}
		
		case 3 :{
				int f;
				printf("Enter the element to be deleted from the list : ");
				scanf("%d",&f);
				new = delete(new,f);
				printf("\nIf you want to continue enter 1, else press any other number : ");
				scanf("%d",&y);		
				break;}			

		case 4 :
			{	
				int x,c;
				printf("\nEnter the element you want to count the appearences of : ");
				scanf("%d",&x);
				c = count(new,x);
				printf("\nThe count of %d is : %d ",x,c);
				printf("\nIf you want to continue enter 1, else press any other number : ");
				scanf("%d",&y);
				break;}
			
		
		case 5 :
			{
				int h,k,z;
				printf("Enter the element you want to enter\n");
				scanf("%d",&h);
				printf("Enter the postion a which you want to insert the number (2-MAX) : ");
				scanf("%d",&k);
				z = insert(h,k,new);
				printf("\nIf you want to continue enter 1, else press any other number : ");
				scanf("%d",&y);		
				break;}
		case 6 :{
				int num;
				struct node *temp = malloc(sizeof(struct node));
				struct node *r =(struct node*)new;
				printf("Enter the number to append at the end of the list : ");
				scanf("%d",&num);		
				temp->value=num;
		                if (new == NULL) /* IF LIST IS EMPTY CREATE FIRST NODE */
		                {
			    		new=temp;
				        new->next =NULL;
		     		}
  				else
		     		{        /* GO TO LAST AND ADD*/

		             		while( r->next != NULL)
			       		r=r->next;
			       		r->next =temp;
			      		r=temp;
			       		r->next=NULL;
		     		}
				printf("\nIf you want to continue enter 1, else press any other number : ");
				scanf("%d",&y);		
				break;}
		case 7 :{
				int x,count,d;
				count = 0;
				d=0;
				printf("\nEnter the element you want the index of : ");
				scanf("%d",&x);
				struct node * p,*k;
				p=new;
				while(p->value !=x)
				{
					if(p->next==NULL)
					{
						if(p->value!=x)
						{
							printf("No such element in list !!!! \n");
							exit(0);
						}
						break;
					}
					count++;
					p=p->next;
					
				}
				/*for(p=new;p!=NULL;p=p->next)
				{
					if(p->value == x)
					{
						for(k=new;k!=NULL;k=k->next)
							count++;
						break;
					}
				}
				for(k=new;k!=NULL;k=k->next)
				{
					d++;
				}
				if(count == d)
				{
					for(p=new;p!=NULL;p=p->next);
					if(p->value !=x)
						printf("\nNo such item in list !!!! \n");
						
				}*/
				printf("The index of the element's first occurence is : %d",count);
				printf("\nIf you want to continue enter 1, else press any other number : ");
				scanf("%d",&y);		
				break;}
		case 8 :{
				reverse(new);
				printf("The reversed list is : \n");
				display(new);
				printf("\nIf you want to continue enter 1, else press any other number : ");
				scanf("%d",&y);		
				break;}
		case 9 :{
				struct node * p;
				int count;
				count = 0;
				for(p=new;p!=NULL;p=p->next)
					count++;
				sort(count);
				printf("\nIf you want to continue enter 1, else press any other number : ");
				scanf("%d",&y);		
				break;}
		case 10 :{
				int z,k;
				printf("Enter the number of elements in the new list : ");
				scanf("%d",&z);
				for(k=0;k<z;k++)
				{
					int num;
					struct node *temp = malloc(sizeof(struct node));
					struct node *r =(struct node*)new1;
					printf("Enter the number to append at the end of the list : ");
					scanf("%d",&num);		
					temp->value=num;
			                if (new1 == NULL) /* IF LIST IS EMPTY CREATE FIRST NODE */
			                {
				    		new1=temp;
					        new1->next =NULL;
			     		}
  					else
			     		{        /* GO TO LAST AND ADD*/
	
			             		while( r->next != NULL)
				       		r=r->next;
				       		r->next =temp;
				      		r=temp;
				       		r->next=NULL;
			     		}
				}
				struct node * p;
				printf("The new list is : \n");
				display(new1);
				/*for(p=new;p!=NULL;p=p->next);
				for(s=new1;s!=NULL;s=s->next)
				{
						
				       		p->next =s;
				      		p=s;
				       		p->next=NULL;

				}*/
				new=extend(new,new1);
				printf("The list after extend is : \n");
				display(new);
				printf("\nIf you want to continue enter 1, else press any other number : ");
				scanf("%d",&y);		
				break;}
		case 11:{
				int s,count,a;
				a=0;
				count = 0;
				printf("\nEnter the index (0-MAX) which you want to pop: ");
				scanf("%d",&s);
				struct node * p;{				
				for(p=new;p!=NULL;p=p->next)
				{
					count ++;
					if(count==s+1)
					{
						a=p->value;
						delete(new,p->value);
						printf("\nThe value popped is : %d",a);
						
						
					}
				}
				}
				printf("\nIf you want to continue enter 1, else press any other number : ");
				scanf("%d",&y);		
				break;}

							
		case 12 :			
  			system("clear");
			exit(0);	
		default : 
			{	printf("\nILLEGAL CHOICE");
				printf("\nIf you want to continue enter 1, else press any other number : ");
				scanf("%d",&y);		
				break;}
			
		        
	}
}while(y==1);	
	/*int MAX;
	printf("Input the number of nodes \n");
	scanf("%d",&MAX);
 	struct node * new = NULL;
	int i = 0;
 	int k; 
 	printf("Enter the linked list elements :");
 	for(i = 0; i < MAX; i++)
 	{
 	 scanf("%d",&k);
 	 new = add(new, k);
 	}
	printf("The elements in the linked list are \n");
	display(new);*/
	return 0;
}
